//QuickSort with a test case.
//By Tripilller, all rights reserved.

#include<iostream>
using namespace std;
int split(int a[],int low,int high)
{
	int i=low;
	int x=a[low];
	for (int j=low+1;j<=high;j++)
	{
		if(a[j]<=x)
		{
			i++;
			if(i!=j)
			{
				int temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
	a[low]=a[i];
	a[i]=x;
	return i;
}
void quickSort(int a[],int low ,int high)
{
	if(low<high)
	{
		int w=split(a,low,high);
		quickSort(a,low,w-1);
		quickSort(a,w+1,high);
	}
}
int main(){
	int n=10;
	int test[]={49,38,65,97,76,13,27,23,2,34};
	cout<<"Original: ";
	for(int i=0; i<n; i++){
		cout<<test[i]<<' ';
	}
	quickSort(test,0,n-1);
	cout<<endl<<"Sorted: ";
	for(int i=0;i<n;i++) {
		cout<<test[i]<<' ';
	}
	cout<<endl;
	return 0;
}